package algorithm.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 四数之和
public class LC18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);

        int a = 0, len = nums.length;
        while (a < len) {
            int b = a + 1;
            while (b < len) {
                int l = b + 1, r = len - 1;
                while (l < r) {
                    long fin = (long) target-nums[a]-nums[b], cur = nums[l] + nums[r];
                    if (cur > fin)
                        r--;
                    else if (cur < fin)
                        l++;
                    else {
                        ans.add(new ArrayList<>(Arrays.asList(nums[a], nums[b], nums[l], nums[r])));
                        l++; r--;
                        while (l < r && nums[l] == nums[l-1])
                            l++;
                        while (l < r && nums[r] == nums[r+1])
                            r--;
                    }
                }
                b++;
                while (b < len && nums[b] == nums[b-1])
                    b++;
            }
            a++;
            while (a < len && nums[a] == nums[a-1])
                a++;
        }
        return ans;
    }

    public static void main(String[] args) {
        LC18 lc18 = new LC18();

        int [] arr = {1000000000,1000000000,1000000000,1000000000};
        List<List<Integer>> list = lc18.fourSum(arr,
                -294967296);
        System.out.println(list);
    }
}
